Optimal design of virtual memory management schemes for applications with dynamic data types, for instance network components, is presented. Said virtual memory management design fits into an overall dynamic memory management design flow. This flow is part of an overall system design flow for embedded hardware/software processors. The overall design flow focuses on data storage and transfer issues and their relation with power consumption and memory size.
Virtual memory management deals with the allocating of a memory block (in which data can be stored) for an application request and recycling the memory block when it is not used anymore by the application. As such the virtual memory concept defines an interface between the application and the physical memory used by the application.
As the power consumption of data-dominated applications (applications in which the power consumption is due to the huge amount of data to be processed and not due to the computation or arithmetic complexity) is heavily dominated by data storage and transfers, systematic design methodologies in which the dynamic storage related issues are globally optimized before doing detailed realization of an embedded processor are needed (F. Catthoor, et al., xe2x80x9cGlobal communication and memory optimizing transformations for low power signal processing systemsxe2x80x9d, IEEE workshop on VLSI signal processing, La Jolla Calif., October 1994. Also in VLSI Signal Processing VII, J. Rabaey, P. Chau, J. Eldon (eds.), IEEE Press, New York, pp.178-187, 1994.) (V. Tiwari, et al., xe2x80x9cInstruction-level power analysis and optimization of softwarexe2x80x9d, Journal of VLSI Signal Processing, No.13, Kluwer, Boston, pp.223-238, 1996.) (R. W. Brodersen, xe2x80x9cThe network computer and its futurexe2x80x9d, Proc. IEEE Int. Solid-State Circuits Conf., San Francisco, Calif., pp.32-36, February 1997.). It is clear that for data-dominated applications with dynamic data types the optimal design of virtual memory management must be part of such an overall design methodology. For RMSP applications much of the memory management can be decided at compile time while according to the subject matter of the present invention the virtual memory management must deal with the memory organization at run-time.
The optimal design of the virtual memory management can be organized in three steps (further called the dynamic memory management design flow). In a first step abstract data types are refined into concrete data types (abstract data type refinement) (S. Wuytack, F. Catthoor, H. De Man, xe2x80x9cTransforming Set Data Types to Power Optimal Data Structuresxe2x80x9d, IEEE Transactions on Computer-aided Design, Vol.CAD-15, No.6, pp.619-629, June 1996.). In the second step (the virtual memory management step) defines a number of virtual memory segments (VMSes) and their corresponding custom memory managers. The third step (the physical memory management stage) assigns these VMSes to a number of allocated physical memories. The present invention deals with the second step, the so-called virtual memory management step.
Different virtual memory management schemes are known in the software community (G. Attardi, T. Flagea, xe2x80x9cA Customisable Memory Management Frameworkxe2x80x9d, Proc. of the USENIX C++ Conference, Cambridge, Mass., 1994.) (P. R. Wilson, et al., xe2x80x9cDynamic Storage Allocation: A Survey and Critical Reviewxe2x80x9d, Proc. Intnl. Wsh. on Memory Management, Kinross, Scotland, UK, September 1995.) but no complete overview of the possible choices is currently available. Moreover for software the main criteria for selection of an appropriate scheme are speed and memory usage whereas for embedded processors power consumption is an important criterion.
In the context of software systems generally applicable (i.e. for all applications, thus not exploiting characteristics of the application) virtual memory management schemes are usual. The only exception is that often the possibility to implement a dedicated virtual memory manager by the user is provided, enabling some exploration. In some cases some libraries of virtual memory management schemes are available (G. Attardi, T. Flagea, xe2x80x9cA Customisable Memory Management Frameworkxe2x80x9d, Proc. of the USENIX C++ Conference, Cambridge, Mass., 1994.). For embedded processors implementing, as focussed in the present invention, a general virtual memory management scheme is not feasible however. A specific scheme for each specific application is necessary.
In the context of software the application is assumed to run on a given hardware architecture while in the present invention virtual memory management design is part of a methodology for design of the hardware. In the software community a given VMM scheme is implemented starting from a predefined memory architecture. For instance, the word size is already defined. Overhead in VMM schemes is likely to be significant, since it is not possible to allocate less than one word for storing information such as used/free or boundary tags. In embedded software or hardware implementations the memory architecture will be defined during the synthesis of the application. For instance, number of memories and memory word sizes are not fixed before synthesis. Thus, overhead can be made as small as the minimum necessary in opposition to fixed architecture target.
In the article by M. Johnstone, P. R. Wilson. xe2x80x9cThe Memory Fragmentation Problem: Solved?xe2x80x9d, Proc. of Object-Oriented Programming Systems, Languages and Applicationsxe2x80x94Wsh. on Garbage Collection and Memory Management, Atlanta Ga., October 1997, a broad comparison between different VMM schemes is presented. These VMM schemes are compared based on the fragmentation caused by each of the mechanisms. It is demonstrated that among the six best schemes, fragmentation is nearly the same and very small. Among these cases, fragmentation could be neglected when compared to overhead necessary for implementing the VMM mechanism. It is assumed in the present invention that also the freedom regarding the number of memories to be used, the number of words needed for each memory, and the memory hierarchy is available for further power optimization.
Known memory-oriented synthesis techniques deal with data types which can easily be analyzed at compile time, for instance multi-media signal processing applications dealing with multi-dimensional array signals. The applications, focussed in the present invention, using dynamic data types, such as network components, in which only a little information is available at compile time, cannot be treated in the same manner. Nevertheless, it is important to exploit the small amount of information as much as possible. Previous work on network components (B. Svantesson, et al., xe2x80x9cModeling and synthesis of operational aid management system (OAM) of ATM switch fabricsxe2x80x9d, Proc. 13th Norchip Conf., pp.115-122, November 1995.) (characterized by dynamic data types) has focussed at low abstraction levels but has not dealt with virtual memory management issues.
Other power-oriented work has been focussing on data-path and control logic design (xe2x80x9cLow power CMOS designxe2x80x9d, (eds. A. Chandrakasan, R. Brodersen), IEEE Press, 1998.) and programmable processors. For the target field of embedded hardware/software processors no such work is known. Previous algorithm-level low power work (S. Wuytack, et al., xe2x80x9cPower Exploration for Data Dominated Video Applicationsxe2x80x9d, Proc. IEEE Intnl. Symp. on Low Power Design, Monterey Calif., pp.359-364, August 1996.) (P. Slock, et al., xe2x80x9cFast and Extensive System-Level Memory Exploration for ATM Applicationsxe2x80x9d, Proceedings 10th ACM/IEEE International Symposium on System-Level Synthesis, Antwerp, Belgium, September 1997.) has focused on signal processing applications.
As a summary it can be stated that the present invention deals with dedicated (application specific) virtual memory management design for data-dominated applications with dynamic data types as part of design of embedded processors (no fixed architecture is given at the stage of the design dealt with by the methods and systems of the present invention).
An aim of the present invention is to provide a systematic procedure and system for selecting a global optimal virtual memory management, taking into account power consideration besides other criteria such as speed and area by addressing this issue at a higher level of abstraction (before detailed compilation and hardware mapping) and focussing on data-dominated applications with dynamic data types, which must be realized in embedded processors.
One aspect of the present invention is a systematic procedure and system for selecting a global optimal virtual memory management scheme from a novel formalized search space representation. The present invention relates to cost effective virtual memory management design for embedded hardware/software processors and data-dominated applications with dynamic data types. Accesses to memory influence power consumption heavily. The cost criterion comprises essentially of (1) the power consumed by the embedded hardware/software processor while executing said application and (2) the overall (memory) size of said hardware/software processor. The hardware/software processor will further also be denoted (as a digital) device.
As input for the design, (concrete or structured) data-types needed by the application are given. The outcome of the design is a number of virtual memory segments and their corresponding memory managers. A virtual memory segment comprises a group of datatypes. For each of said group of datatypes a virtual memory manager may be designed. It must be emphasized that thus two major steps can be indicated: (1) deciding on the grouping of said datatypes and (2) designing virtual memory managers for each said group.
Virtual memory management schemes in general deal with the allocation of a memory block (in which data types can be stored) for an application request and recycling the memory block when it is not used anymore by the application. The virtual memory management tries to avoid (external and internal) fragmentation of the memory. Note that the virtual memory management defines an interface between the dynamic allocation of data in the application and the physical memory of the processor.
Before cost effective design of the virtual memory management (both grouping of datatypes and virtual memory manager design) can be performed, a clear insight into the distinct design choices must be available. In the present invention the search space is organized as a limited set of decision trees. Selecting a leaf from each of said trees and combining the selected leaves results always in a valid virtual memory management scheme. When design choices which are intermediate the design choices indicated by the leaves are possible, this is explicitly indicated by a mark. As such the set of decision trees with their leaves and marks describes the complete search space by presenting all independent (orthogonal) design choices.
The actual choices to be made by a designer can be guided by (1) using compile-time information (e.g. worst case size of data types), (2) profiling information (e.g. access counts and size of data types) and (3) estimates of the needed memory size and power consumption. Said profiling information is obtained by performing simulations, using input sequences for said application. Said estimation of the needed memory size and power consumption are essentially depending on said profiling information.
The results of said simulations (the profiling information) can depend heavily on the virtual memory management construction used and that said virtual memory management is just under construction here. Therefore, the design methodology requires a simulation environment in which an application can be simulated using a selected virtual memory organization (defining virtual memory segments by deciding which data types are in which pool) and selection for all pools of the corresponding virtual memory managers. From these simulations profiling information of the application under study is extracted. In these simulations real data (input sequences representative for the data that will be used by the application when it is fully realized) is used. These simulations are also called experiments.
A second aspect of the present invention is to present a methodology for optimal design of a virtual memory management, based on exploration of a structured (orthogonal) complete search space of virtual memory organization and management schemes. Said structured (orthogonal) complete search space of virtual memory organization and management schemes is presented as a list of disjunct trees, each representing a design choice. The decision to be made by the designer can be guided either by experiments or can be a standard or default solution. Note that it is the designers choice to determine how to decide. The designer can also decide not to perform an experiment at all.
A third aspect of the present invention is to present a methodology and a design system for optimal design of a virtual memory management, based on exploration of a structured (orthogonal) complete search space of virtual memory organization and management schemes, in such a way that the decision to be made is based either on experiments or a standard solution and the designer determines how to decide.
As indicated above design decisions made can be based on the profiling information found by experiments, based on simulations. Simulations are is in principle only possible when for all design choices a particular choice is made and as such a virtual memory management is determined. But it is these design choices which are under investigation in accordance with the present invention. In the present invention this chicken-and-egg problem is solved as follows. A distinction between the leaf of the tree under consideration and the other leaves is made. Experiments are defined as simulations for which a variety of virtual memory management schemes are used, whereby only said leaf of the tree under consideration is varied. The other leaves, necessary for defining a virtual memory management are fixed. When such a leaf is part of a tree for which already an optimal leaf is determined, naturally said leaf is said optimal leaf. When such a leaf is part of a tree for which an optimal leaf has not yet been determined, a default leaf is used. Naturally, experimenting is only possibly when a suitable simulation environment is available.
A fourth aspect of the present invention is to present a methodology for optimal design of a virtual memory management, based on exploration of a structured (orthogonal) complete search space of virtual memory organization and management schemes, whereby the experiments are performed in a particular way.
The experimentation method presented above fits into a step-by-step approach of virtual memory management design. Moreover, the experimentation method relies heavily on the assumption that choices fixed at a previous step need not be reconsidered while proceeding through the step-by-step method. This is an essential feature of the tree ordering, presented in the present invention further on.
The most important decision in the design of virtual memory management (for dynamic data-type applications) is choosing between one sector (virtual memory segment) per data type or using an entire pool (virtual memory segment) for all types or some intermediate solution. This decision has severe influences on the other choices influencing the cost criterion. The organization of the virtual memory is thus the first decision which must be made. Organizing the virtual memory means deciding on the grouping of datatypes in groups. For each group a virtual memory segment is defined. For each segment a virtual memory manager must be constructed.
A fifth aspect of the present invention is to present a methodology for optimal design of a virtual memory management, based on exploration of a structured (orthogonal) complete search space of virtual memory organization and management schemes, in a step-by-step manner, whereby in a first step a decision on the organization of the virtual memory is made.
In general power consumption models are linear in access count and sublinear in memory size. As power consumption is one of the essential parts of the cost criterion under consideration, the characteristics of the power consumption model influences the virtual memory management design. Indeed, in the present invention a major distinction is made between access dominated and size dominated data types. Note that based on information (compile-time or profiling information obtained from experiments) data types are labeled to be either access dominated or size dominated. In the present invention a particular way of grouping is proposed as a standard solution based on said classification.
A sixth aspect of the present invention is to present the structure of the tree, representing the design choice, related to grouping of datatypes.
A seventh aspect of the present invention is that it is proposed to place each access count dominated data type in a separate group (pool, sector, virtual memory segment) and to group all size dominated data types in one group (pool, sector, virtual memory segment).
An eighth aspect of the present invention is as second step in virtual memory management design deciding for each grouping of datatypes which type of index ordering will be used.
A ninth aspect of the present invention is to present the structure of the tree, representing the design choices, related to index ordering.
A tenth aspect of the present invention is that it is proposed for access count dominated data types to use index ordering.
A third step in virtual memory management design is to decide for each grouping of datatypes which type of merging and splitting policy is made.
A eleventh aspect of the present invention is that in the methodology for optimal design of a virtual memory management, the decision about merging and splitting for each group of datatypes is recognized as the third decision to be taken.
A structure for each of said disjunct decision trees is proposed. Said trees are organized hierarchically and thus comprise several branches, subbranches and leaves. Leaves are the lowest elements of said trees in said hierarchical ordering. Marks indicate whether intermediate design choices between the design choices, represented by leaves or branches are possible.
Another approach for designing a cost effective virtual memory management is instead of exploring the full design space, defining a parametrizable virtual memory manager model and tuning the parameters of this model for the application under consideration. As such a limited search space, spanned by the parameters, is defined. Naturally the model must be chosen such that the cost optimization is still feasible.
A twelfth aspect of the present invention is that a method for designing an optimal virtual memory manager which is based on tuning of a parametrizable virtual memory management model is presented.
A thirteenth aspect of the present invention is that a particular virtual memory management model is presented.
To summarize it can be stated that in the present invention a systematic design methodology and design system for cost effective virtual memory management is presented. The methodology and system are based on a representation of all possible design choices as a limited set of disjunct trees. Selection of a leaf of each of said disjunct trees defines a valid virtual memory management. Said limited set of disjunct trees is presented. In the present invention it is recognized that selection of a leaf of one of said trees, depends either on experiments or is just a standard leaf selection. In the present invention a particular way of experimenting is disclosed. Said experimentation approach fits into a step-by-step design procedure. In the present invention it is recognized that virtual memory organization is the first basic step. The tree, representing said design choice, is presented. A standard leaf selection, representing an ad-hoc design rule for organizing the virtual memory is also given. Next index-ordering is put forward as the second decision to be taken. The tree, representing said design choice, is presented. An ad-hoc solution for access count dominated datatypes is presented. Further deciding on the merging and splitting policy is presented as the third decision to be taken. The structure of each of said disjunct trees are presented. Another design approach is based on a parametrizable model for the virtual memory. The parameters of this model can be explored during design. Both this method and a particular model are presented.
The present invention can be formalized as follows:
A method for designing an optimal virtual memory management for an application, comprising the steps of:
representing all virtual memory management design choices in a set of disjunct trees, each of said trees presenting an orthogonal design choice, the leaves of a tree representing the design options of the corresponding design choice, such that any combination of said leaves from said disjunct trees defines a valid virtual memory management, whereby said combination comprises one said leaf from each of said disjunct trees; and
selecting from all disjunct trees one leaf, thereby defining said optimal virtual memory management.
The application is to be executed on an essentially digital circuit or device. It is this digital circuit or device which is under design or construction in accordance with the present invention. The virtual memory management design task is part of the overall design flow for said digital circuit or device. Therefore, the present invention can also be described as a method for designing an optimal virtual memory management for an application to be executed on an essentially digital circuit.
Said virtual memory management being designed is optimal with respect to an optimization function. For example, at least the power consumption of said digital device while said application is being executed on said digital device is taken into account. Further the total memory size can be part of said optimization function.
A virtual memory manager can be described as a set of rules or policies being used while dealing with memory occupation. However, virtual memory management does not deal directly with the physical memory of said digital device or circuit but with a virtual memory. The assignment of the physical memory of said digital device to said virtual memory is done after the virtual memory design. The virtual memory manager defines a plurality of virtual memory segments. The physical memory comprises a plurality of physical memories. The assignment can be one physical memory for one virtual memory segment but this is certainly not necessary.
Therefore, the present invention can also be described as a method for designing an optimal virtual memory management for an application to be executed on an essentially digital circuit, said optimal virtual memory management being related to the physical memory of said digital circuit.
FIG. 17 shows as an example a digital device (10), comprising a processor (20) and a physical memory (30). The physical memory comprises two physical memories (40), (50). On said digital device (10) an application runs or is executed. Said application is represented as a set of instructions (60). A part of said instructions are operations on variables and thus invoke memory manipulations. The virtual memory (70) comprises in this example of three virtual memory segments (80), (90), (100). Each of said virtual memory segments are a grouping of variables involved in the execution of said application. Note that the actual assignment of memory to said groups of variables is not based on a one physical memory for one virtual memory segment relationship. To each of said virtual memory segments a set of rules (110), (120), (130), defining the memory management policy of said virtual memory segments is associated.
The choice of how to group the variables or datatypes involved in the execution of the application and the selecting of the virtual memory management of each of said groups defines the virtual memory management design problem.
In the present invention the design choices are represented as a set of disjunct trees (e.g., tree 1 (130) and tree 2 (140) in the example), being orthogonal to each other, meaning that the selection of a leaf of a tree is always possible irrespective of the choice of a leaf of another tree without affecting the result. However, the order of selection may influence the result. It must be emphasized that the orthogonality of said trees concerns the possibility to select a leaf, and not about the actual choice of the leaves while determining an optimal virtual memory management with respect to an optimization function. It can be said that any combination of said leaves of said disjunct trees defines a valid virtual memory management, meaning that such combination can be realized in practice.
The set of disjunct tree can be enumerated as follows:
a tree, representing how the virtual memory is organized;
a tree, representing the fit policy;
a tree, representing the match policy;
a tree, representing the block size of free blocks;
a tree, representing free block tracking policy;
a tree, representing the index ordering policy;
a tree, representing the freeing used blocks policy;
a tree, representing the block splitting policy;
a tree, representing the block size used in the splitting policy;
a tree, representing the part of the free block used first in the splitting policy;
a tree, representing the index ordering used in the splitting policy;
a tree, representing the block merging policy;
a tree, representing the block size used in the merging policy;
a tree, representing the amount of merging to be done;
a tree, representing the index ordering used in the merging policy; and
a tree, representing the recording policy.
A method being based on a tree by tree optimization is exploited. The selection of one leaf of a tree may be based either on experiments or a standard leaf selection.
FIG. 18 shows an example of said tree by tree optimization. The search space is here represented by three disjunct trees. The tree ordering is indicated with their tree number. The first tree has three design options. The second and third tree have each two design options. The arrow from top to bottom indicates the different steps during the design procedure. In a first step experiments are performed by extracting experimental results (being values of the optimization function) for the different design options represented by tree one while default design options are selected from the other trees. From said experimental results the designer makes a conclusion about the design choice to be selected for the first tree. In a second step again experiments are performed by extracting experimental results for the different design options represented by tree two while using the selected design choice of tree one and a default design option for tree three. The last step of the example shows that the previous kind of experimentation is not necessarily needed. Indeed, for the selection of a design choice of tree three just a standard design choice is selected. Such a standard design choice can be based on knowledge of the application, for instance also extracted via some other type of experimentation, for instance determining profiling information about the data types.
The approach via extracting values of the optimization function is described as follows. The selection of one leaf of a tree, based on experiments further comprises the steps of: loading said application in a simulation environment, enabling performance of experiments for said application combined with a variety of experimental virtual memory managements;
performing experiments whereby all leaves of said tree from which one leaf will be selected are selected once, for all trees of said set of disjunct trees, except said tree from which one leaf will be selected, an optimal leaf is selected when available, otherwise a default leaf is selected, said selected leaves of all said disjunct trees defining an experimental virtual memory management;
calculating the cost criterion for each experiment; and
selecting said leaf resulting in the most optimal cost criterion.
The tree related to the virtual memory organization is the first one to be treated in the tree by tree approach and has a particular structure as described below. The tree representing how the virtual memory is organized comprises:
a first leaf, representing a first design choice such that for each datatype of said application another pool is used;
a second leaf, representing a second design choice such that all datatypes of said application are in one pool; and
a mark, indicating that each design choice in between said first and second design choice is valid.
Next a standard leaf selection approach is presented. Indeed after experimentation with a default virtual memory management, some properties or knowledge of the application is extracted, for example access count and size of data types. From this knowledge a leaf selection is determined without extracting information of the optimization function. Such an approach can be described as follows: The determination of the organization of the virtual memory, comprises:
grouping all datatypes in one pool;
performing an experiment with a default virtual memory manager for said pool;
indicating for each datatype whether its is access count dominated or size dominated;
defining for each access count dominated datatype a pool; and
defining one pool for all size dominated datatypes.
The tree related to the index ordering policy is the second one to be treated in the tree by tree approach and also has a particular structure. The tree representing the index ordering policy comprises:
a first leaf, representing a first design choice, such that no index is used; and
a second leaf, representing a second design choice, such that an index is used.
A standard leaf selection for access count dominated data types is presented. Notice that this requires again some experimentation in order to determine which data types are access count dominated with either a default virtual memory manager or potentially a virtual memory manager wherein already the design choices of the first design step is taken into account. The index ordering policy of the virtual memory manager for an access count dominated datatype uses an index.
The tree related to the merging and splitting policy is the third one to be treated in the tree by tree approach. In this third step, leaves are selected from the trees related to the block merging and block splitting policy, thereby no ordering of said trees, related to merging and splitting must be respected when selecting said leaves.
The structure of the trees is depicted below:
The tree, representing the block size of free blocks, comprises:
a first leaf representing that said block size of free blocks is fixed;
a second leaf, representing that said block size of free blocks is free.
The tree, representing the free block tracking policy, comprises:
a first branch, representing the use of lookup tables;
a second branch, representing the use of link fields said branches are connected by a mark;
said first branch comprises a first leaf, representing the use of state variables, and a second leaf, representing the use of tables;
said second branch comprises a first leaf, representing a simple linked approach and a second leaf, representing a double linked approach.
The tree, representing the index ordering policy, comprises:
a first leaf, representing that no index is used;
a branch, representing completely indexing;
said first leaf and branch are connected by a mark said branch, comprises a first leaf, representing address indexing, a second leaf, representing size indexing and a third leaf, representing other indexing approach; said leaves are connected by a mark.
The tree, representing the recording policy, comprises:
a first leaf, representing no recording;
a branch, representing recording via a header;
a second leaf, representing recording via boundary tags;
said branch, comprises a first leaf, representing that the block size is recorded, a second leaf, representing that whether the block is free or not is recorded and a third leaf, representing that other information is recorded.
The tree, representing how the virtual memory is organized, comprises:
a first leaf, representing that for each datatype another pool is used;
a second leaf, representing that all datatypes are in one pool;
said leaves are connected by a mark.
The tree, representing the match policy, comprises:
a first leaf, representing an exact match policy;
a second leaf, representing an approximate match policy.
The tree, representing a fit policy, comprises:
a first leaf, representing a first fit policy;
a second leaf, representing a next fit policy;
a third leaf, representing a best fit policy;
a fourth leaf, representing a worst fit policy;
said third and fourth leaf are connected by a mark.
The tree, representing the freeing used blocks policy, comprises:
a first leaf, representing a LIFO ordering approach;
a second leaf, representing a FIFO ordering approach;
a third leaf, representing an indexed ordering approach;
said first and second leaf are connected by a mark.
The tree, representing the block splitting policy, comprises:
a first leaf, representing an approach that never splits;
a second leaf, representing an approach, which always splits;
said leaves are connected by a mark.
The tree, representing the block size used in the splitting policy, comprises:
a first leaf, representing small block sizes;
a second leaf, representing large block sizes;
said leaves are connected by a mark.
The tree, representing the part of the free block used in the splitting policy, comprises:
a first leaf, representing that the first part of the block is used;
a second leaf, representing that the last part of the block is used;
said leaves are connected by a mark.
The tree, representing the index ordering used in the splitting policy, comprises:
a first leaf, representing that the index ordering is respected;
a second leaf, representing that no index is respected.
The tree, representing the block merging policy, comprises:
a first leaf, representing immediate block merging;
a second leaf, representing never merging;
a branch, representing deferred merging;
said branch, comprising of a second leaf, representing waiting for a fixed amount of requests, a third leaf representing waiting for a variable amount of requests, and a fourth leaf, representing waiting for an unsatisfied request.
The tree, representing the block size used in the merging policy, comprises:
a first leaf, representing a large block size;
a second leaf, representing a small block size;
said leaves are connected with a mark.
The tree, representing the amount of merging to be done, comprises:
a first leaf, representing that all mergeable blocks are merged;
a second leaf, representing that enough merging is done to satisfy a request;
said leaves are connected with a mark.
The tree, representing the index ordering used in the merging policy, comprises:
a first leaf, representing that the index is respected;
a second leaf, representing that no index is respected.
The further formalized description below refer to the optimal design method based on a parametrizable model. The present invention includes a method and a system for designing an optimal virtual memory management for an application, comprising:
loading said application in a simulation environment, enabling performing of experiments for said application combined with a virtual memory management;
defining a virtual memory management model with a set of parameters;
performing experiments using a default virtual memory management; and
selecting said parameters based on said experiments.
In this method said virtual memory management model consists of
pools of a first kind and pools of a second kind;
said pools of a first kind acts as cache for said pools of a second kind;
said pools of a first kind consists of:
pools of a first type with a variable number of blocks;
pools of a second type with a fixed number of blocks; and
the number of pools of the first type, the number of pools of the second type, the number of blocks in the pools of the second type, the initial number of blocks in the pools of the first type, the number of pools of a second kind and the size of the blocks in said pools of a second kind are parameters of said virtual memory management model.
The blocks are connected either in a list, a binary tree or a pointer array. The pools of a second type are used for access count dominated datatypes and said pools of a first type are used for size dominated datatypes. The number of blocks transferred between pools of a first kind and pools of a second kind and vice versa, is a parameter of said virtual memory management.
Naturally the approach via the parametrized model fits in the general approach as each parameter of said model can be represented by tree, with a first leaf, indicating a minimum value and a second leaf, indicating a maximum value, and a mark, indicating that intermediate value between said minimum and maximum value are possible. By definition said trees are disjunct and every selection of said parameters and thus leaf selection defines a valid memory management. Therefore the approach via the parametrized model can be formalized as follows: each of said trees of said set of disjunct trees is related uniquely to the parameters of a virtual memory management model. The virtual memory management model may consists:
pools of a first kind and pools of a second kind;
said pools of a first kind acts as cache for said pools of a second kind;
said pools of a first kind consists of:
pools of a first type with a variable number of blocks;
pools of a second type with a fixed number of blocks; and
said set of disjunct trees comprises at least of:
a tree related to the number of pools of the first type;
a tree related to the number of pools of the second type;
a tree related to the number of blocks in the pools of the second type;
a tree related to the initial number of blocks in the pools of the first type
tree related to the number of pools of a second kind and the size of the blocks in said pools of a second kind are parameters of said virtual memory management model.